package cn.com.yang.datastruct.wgraph;


/**
 * 带权图 难度系数9.0
 * 
 * @author yangyijin
 * @since 2024年2月8日-上午9:40:41
 */
public class WGraph {
	// 图的订单和边，边是二维矩阵或者邻接表
	private Vertex[] vertexs;
	private int[][] adjMatix;
	private int nVertex;// 计数器，定点的个数
	private final int MAX_VERTEX = 20;// 最大的顶点个数

	private PriorityQueue priorityQueue;// 优先接队列
	private int nTree;// 已经求解到的最小生成树的顶点的下标

	private int currVertex;// 当前顶点的下标
	
	private final int INF=1000000;//初始化很大的数

	public WGraph() {
		vertexs = new Vertex[MAX_VERTEX];
		adjMatix = new int[MAX_VERTEX][MAX_VERTEX];
		for (int i = 0; i < MAX_VERTEX; i++) {
			for (int j = 0; j < MAX_VERTEX; j++) {
				adjMatix[i][j] = INF;
			}
		}
		nTree=0;
		nVertex = 0;
		priorityQueue = new PriorityQueue();
	}

	// 向顶点插入数据
	public void insert(char label) {
		vertexs[nVertex++] = new Vertex(label);
	}

	// 有了顶点够，更新矩阵关系
	public void addEdge(int start, int end,int price) {
		// 注意这里要更新的两个部分，倒三角
		adjMatix[start][end] = price;
		adjMatix[end][start] = price;
	}

	// 打印指定顶点中的label
	public void displayVertex(int v) {
		System.out.print(vertexs[v].label);
	}
	//求解带权值的最小生成树，结果找到输出
	public void mstw() {
		//一般选择第一个顶点作为起始点
		currVertex = 0;
		//U ={A,D,B} , TE={(A,D),(B,D)}
		while(nTree<nVertex-1) {
			vertexs[currVertex].inInTree = true;//相当于把此顶点放入U集合
			nTree ++;
			for(int i = 0;i<nVertex;i++) {
				if(i==currVertex) continue;//遍历到自己不做操作
				int price = adjMatix[currVertex][i];//对应边cuurVertex---i的权值
				if(price==INF) continue;
				//剩下的情况，当前点的邻接点
				//把这些边插入到优先队列里
				priorityQueue.insert(new Edge(currVertex, i, price));
			}
			//1.细节考虑1
			//要把已经放到U集合中的顶点，为边的起点和终点的边，从优先队列中删除
			for(int i=0;i<priorityQueue.getSize();i++) {
				if(vertexs[priorityQueue.peekN(i).startVert].inInTree
						&& vertexs[priorityQueue.peekN(i).endVert].inInTree) {
					priorityQueue.removeN(i);//边的起点 终点 同时都在U集合中吗，应该从优先级队列删除这条边
				}
			}
			//2.细节考虑2
			if(priorityQueue.getSize()==0) {
				//出错了
				System.out.print("当前顶点一个邻接点都没有，没有最小生成树");
			}
			
			Edge minEdge = priorityQueue.removeMin();//拿到最小的边
			int startV = minEdge.startVert;
			currVertex = minEdge.endVert;
			//打印输出找到的边，相当于把目标边放到原理的TE集合，(理论，不做存储)
			System.out.print(vertexs[startV].label);
			System.out.print(vertexs[currVertex].label);
			System.out.print(" ");
		}
		//上面的循环把所有项的顶点的isIntree=true，还原
		for(int i=0;i<nVertex;i++) {
			vertexs[i].inInTree=false;
		}
		
	}
}
